package _220401;

import java.util.Scanner;

/**
 * @author ShadowLim
 * @create 2022-04-01-21:09
 */
public class 最优包含 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String S = scan.nextLine();
        String T = scan.nextLine();
        int n = S.length();
        int m = T.length();
        int dp[][] = new int[n+1][m+1]; // dp[i][j]表示S串中前i个字符，包含有T串中前j个字符最少需要修改的字符个数。
        S = " "+S;
        T = " "+T;
        for (int i = 0; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = (int)1e8;
            }
        }
        /**
         * 如果S[i]=T[j] ,那么T串中的最后一位要么让他和S[i]相等，要么让他和前面的相等。
         * dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])
         * 如果S[i]!=T[j],那么要么是让T[j]和S串前面的字符一样，要么修改S[i]。
         * dp[i][j]= min(dp[i-1][j-1]+1,dp[i-1][j])
         */
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (S.charAt(i) == T.charAt(j)) {
                    //相等不用改
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    //要么改，要么s前i-1个字符已经包含了t前j个字符
                    dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1] + 1);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}
